package algorithm.dp;

public class 最长上升子序列 {
    /*
     * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
     * 
     * 示例:
     * 
     * 输入: [10,11,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 说明:
     * 
     * 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到
     * O(n log n) 吗?
     */
    public int lengthOfLIS(int[] nums) {
        return dp2(nums);
    }

    int dp2(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len + 5];
        // dp[i] ：表示序列长度为i中最后一个数最小的值
        int maxLen = 0;
        for (int i = 0; i < len; i++) {
            int index = search(dp, nums[i], 0, maxLen);
            if (index == maxLen) {
                maxLen++;
                dp[maxLen] = nums[i];
            } else {
                dp[index + 1] = Math.min(dp[index + 1], nums[i]);
            }
        }
        return maxLen;
    }

    int search2(int[] dp, int max, int i, int j) {
        while (true) {
            if (dp[j] < max) {
                return j;
            }
            if (i == j || i + 1 == j) {
                return i;
            }
            int mid = (i + j) >> 1;
            if (dp[mid] < max) {
                i = mid;
            } else {
                j = mid;
            }
        }
    }

    int search(int[] dp, int max, int i, int j) {
        if (dp[j] < max) {
            return j;
        }
        if (i == j || i + 1 == j) {
            return i;
        }
        int mid = (i + j) >> 1;
        if (dp[mid] < max) {
            return search(dp, max, mid, j);
        } else {
            return search(dp, max, 0, mid);
        }
    }

    int dp(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len + 5];
        // dp[i] 长度为i数字序列，最长上升子序列
        int maxLen = 0;
        for (int i = 1; i <= len; i++) {
            int max = 0;
            for (int j = i - 1; j >= 1; j--) {
                if (nums[i - 1] > nums[j - 1]) {
                    max = Math.max(max, dp[j]);
                }
            }
            dp[i] = max + 1;
            maxLen = Math.max(dp[i], maxLen);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        最长上升子序列 run = new 最长上升子序列();
        int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
        run.lengthOfLIS(nums);
    }
}
